package Test;
//给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//示例 1：
//输入：nums = [1,5,11,5]
//输出：true
//解释：数组可以分割成 [1, 5, 5] 和 [11] 。
//示例 2：
//输入：nums = [1,2,3,5]
//输出：false
//解释：数组不能分割成两个元素和相等的子集。
public class test02 {
    class Solution {
        public boolean canPartition(int[] nums) {
            //1.创建dp表
            //2.初始化
            //3.填表
            //返回值
            //处理特殊情况
            int n = nums. length,sum = 0;
            for(int x : nums)sum += x;
            if(sum % 2 == 1)return false;
            int aim = sum / 2;
            boolean[] dp = new boolean[aim +1];
            //初始化
            dp[0] = true;
            for(int i = 1;i <= n;i++){
                for(int j = aim; j >= nums[i - 1];j--){
                    dp[j] = dp[j] || dp[j - nums[i - 1]];
                }
            }
            return dp[aim];
        }
    }
}
